package com.example.demo.arithmetic.algorithm.stack;

import javax.validation.constraints.NotNull;
import java.util.Stack;

/**
 * Description: 栈实现排序<br/>
 *
 * @author liulonglong<br       />;
 * @taskId <br/>
 * @Date 2019/5/14 14:02
 * @Version 1.0
 */
public class StackSort {
    //双栈排序
    public static Stack<Integer> twoStackSort(@NotNull Stack<Integer> s) {
        Stack<Integer> stack = new Stack<Integer>();
        while (!s.isEmpty()) {
            int tmp = s.pop();
            while (!stack.isEmpty() && stack.peek() > tmp) {
                s.push(stack.pop());
            }
            stack.push(tmp);
        }
        return stack;
    }

    public static void main(String[] args) {
        Stack<Integer> s = new Stack<Integer>();
        s.push(5);
        s.push(4);
        s.push(7);
        s.push(8);
        s.push(6);
        s.push(1);
        s.push(9);
        s.push(2);
        s.push(3);
        Stack<Integer> stack = twoStackSort(s);
        System.out.println(stack);
    }

}
